By

文章目录
  1. 1. Brute Force
  2. 2. HashMap
  3. 3. Two Pointer

本系列代码见我的Leetcode仓库

tags: [Array,Hash Table]

填坑第一作，坑在这里
以后都假设大家都看过题目了，我会大略说一下题意，注意点，解法，但是就不搬运题目了。

Two Sum是一个经典的数列问题，它可以直指高斯消元法。本题是一个最简单的情况，给定一个数列和一个目标，在数列中找到两个数，使得他们的和等于目标，返回这两个数的序号（从0开始计）。

虽然是简单的题，但我说话比较啰嗦，就说一下我的想法。此题乃至一般题，首先想到判空，如果数列中不存在目标数怎么处理。因为是在Leetcode上可以无限试，特别是现在开了模拟coding run之后，所以完全可以构造一个用例看看Leetcode对于这种情况他是怎么处理的。然后考虑多个解的情况，怎么处理。我做的时候，他题目中有很强的假设，说有且仅有一个解。如果在面试的过程中遇到这种题，需要向面试官明确以上条件，不但可以简化实现，同时也可以反映出你的思路，一般来说面试时很少遇到这么简单的题，如果遇到那么你在别的方面的表现可能就是你取胜之处。

考虑了不存在的情况后，考虑正常情况。可以有几种解法：

Brute Force

最容易想到暴力解法，固定一个元素，遍历其余元素，找到满足条件的就返回。这种解法最坏情况是N^2时间复杂度。但是这是帮助自己理清思路的好方法，特别是当问题较为复杂的时候，如果有暴力解法能写出来，再在这个基础上优化也是好的。在面试的时候，面试官对于这种优化行为也是较为欣赏。怎么说呢，暴力解法就像是及格线，需要熟练掌握，但是未必需要亮出来。

HashMap

HashMap总体上跟暴力解法相似，但是进行了优化。我们在暴力解法中，事实上有过很多重复计算，如果能把这些计算保存下来必然可以减少复杂度，HashMap就是在这种情况下想到的。

解法是先预处理，将数组每个元素相对于目标的差值及其对应的下标存入Map，时间O(N)。
然后从头开始看每个元素是否都已经存在于Map中，这一步是N*O(1)。如果存在则说明找到解，可以返回序号。
需要注意的是判断两个下标是否指向同一个元素，如果是则跳过。
总体复杂度是O(2N)

Two Pointer

有没有更巧妙的方式呢？有，就是Two Pointer。但是Two Pointer的解法依赖于有序数组，而题目中没有这个信息，所以这种算法在这个题不一定是最好的，但是这是一种非常巧妙的思想，可以在一遍扫描就完成求解。

Two Pointer的基本思路，就是在有序数组上，左右设置指针，对向移动，当指针相遇则算法结束。无比经典的快速排序就是基于Two Pointer和Recursive的方式。

对于求和，不妨先假设数组升序，那么设置left和right指针，对向移动，看left和right指向的数之和是否等于目标，如果是则返回，如果大了则right指针移动，小了则left指针移动，指针相遇说明无解。这个算法的正确性可以很简单地证明：假设相遇时存在解，那么可以假设至少其中一个指针曾停留在其中一个解上，不妨假设是left指针在较小的解上，此时如果right指针在另一个解左边，则和小于目标，不可能移动right，而right在另一个解的右边时则和大于目标，应当移动right，必然到达另一个解，与假设矛盾。

至此思路清晰，将数组排序，然后使用双指针跑一遍即可得到解，总体时间复杂度是O(logN+N)，如果原本就有序则可更优。
需要注意的是排序前保留序号和数值对应关系，同时注意可能有重复元素，所以需要以链表方式存储。

Two Pointer算法可以扩展到含有重复元素的数组，可以扩展到双向链表，可以修改为同向指针应用于链表有无环判断，可以扩展到Three Pointers，可以扩展到适用于N Sum问题，可以结合回溯法解最优化问题。可以说是非常简洁有用的算法。

文章目录
  1. 1. Brute Force
  2. 2. HashMap
  3. 3. Two Pointer